#pragma once

#include "../common.hpp"

namespace zzz{
//Fibonacci Heap is a fast heap that you can insert data and extract the minimal data sequentially
//data in the heap can be decreased but never increased
//Simple Usage:
//heap.Insert(value)
//while(!heap.IsEmpty()) value=heap.ExtractMin();

//////////////////////////////////////////////////////////////////////////
// Fibonacci Heap Node Class
//////////////////////////////////////////////////////////////////////////

template<typename T>
class FibonacciHeap;

template<typename T>
class FibonacciNode
{
  friend class FibonacciHeap<T>;
public:
  FibonacciNode()
  :parent(NULL),child(NULL),degree(0),mark(0),delete_flag(0)
  {
    left=this;
    right=this;
  }

  ~FibonacciNode(){}

  void operator=(const T &v)
  {
    key = v; //this need to be implemented if T is a class
    delete_flag = 0;
  }

  void operator=(FibonacciNode<T>& other)
  {
    key=other.key;
    delete_flag = other.delete_flag;
  }

  bool operator<(FibonacciNode<T>& other)
  {
    if (delete_flag==1 && other.delete_flag==0) return true;  //-inf<any number
    if (other.delete_flag) return false;  //nothing < -inf
    return key < other.key;  //this need to be overload if T is a class
  }

  const T& GetKey(){return key;}
protected:
  FibonacciNode *left, *right, *parent, *child;
  short degree;
  unsigned char mark, delete_flag;
  
  //link to the left of other
  //ATTENTION: not link this single node, but the whole chain
  //if you only want to link a single node, need to set the right and left of this node to itself
  void LinkToLeft(FibonacciNode<T> *other)
  {
    //right side
    right->left=other->left;
    other->left->right=right;
    //right side
    right=other;
    other->left=this;
    //parent
    parent=other->parent;
  }

  //get out of the loop and link left to right
  void Unlink()
  {
    left->right=right;
    right->left=left;
    left=NULL;
    right=NULL;
  }

  T key;

};

//////////////////////////////////////////////////////////////////////////
// Fibonacci Heap Class
//////////////////////////////////////////////////////////////////////////

template<typename T>
class FibonacciHeap
{
private:
  FibonacciNode<T> *MinRoot;
  long NumNodes, NumTrees, NumMarkedNodes;

public:
  typedef FibonacciNode<T> NodeType;
  FibonacciHeap():MinRoot(NULL),NumNodes(0),NumTrees(0),NumMarkedNodes(0)
  {}

  virtual ~FibonacciHeap()
  {
    Clear();
  }

  void Clear()
  {
    while (MinRoot != NULL)
    {
      FibonacciNode<T>* Temp = ExtractMinNode();
      delete Temp;
    }
    MinRoot=NULL;
  }
  // The Standard Heap Operations
  // simple interface
  bool IsEmpty(){return NumNodes==0;}

  FibonacciNode<T> *Insert(const T &v)
  {
    FibonacciNode<T> *NewNode=new FibonacciNode<T>;
    NewNode->key=v;
    InsertNode(NewNode);
    return NewNode;  //return node address, so that DecreaseKey can be done
  }

  const T ExtractMin()
  {
    FibonacciNode<T>* m=ExtractMinNode();
    T v=m->key;
    delete m;
    return v;
  }

  inline const T& Minimum()
  {
    return MinRoot->key;
  }

  // node manipulation interface
  void InsertNode(FibonacciNode<T> *NewNode)
  {
    if (NewNode == NULL) return;

    // If the heap is currently empty, then new node becomes singleton
    // circular root list
    if (MinRoot == NULL)
      MinRoot = NewNode->left = NewNode->right = NewNode;
    else
    {
      NewNode->LinkToLeft(MinRoot->right);

      // The new node becomes new MinRoot if it is less than current MinRoot
      if (*NewNode < *MinRoot) MinRoot = NewNode;
    }

    // We have one more node in the heap, and it is a tree on the root list
    NumNodes++;
    NumTrees++;
    NewNode->parent = NULL;
  }

  FibonacciNode<T>* ExtractMinNode()
  {
    FibonacciNode<T> *Result = MinRoot;

    // Remove minimum node and set MinRoot to next node
    if (Result  == NULL) return NULL;

    MinRoot = Result->right;
    Result->Unlink();
    
    if (Result->child == NULL && MinRoot == Result)  //No child and this is the only root, tree goes empty
      MinRoot = NULL;
    else if (MinRoot == Result)  //this is the only root, children became roots
      MinRoot = Result->child;
    else if (Result->child != NULL)  //need to link children to root chain
      Result->child->LinkToLeft(MinRoot->right);

    //clear node
    NumNodes --;
    if (Result->mark)
    {
      NumMarkedNodes --;
      Result->mark = 0;
    }
    Result->degree = 0;
    Result->child = Result->parent = NULL;

    //consolidate tree
    if (MinRoot != NULL) Consolidate();

    return Result;
  }

  //ATTENTION: This will delete OtherHeap
  void Union(FibonacciHeap<T> *OtherHeap)
  {
    if (OtherHeap == NULL || OtherHeap->MinRoot == NULL) return;

    OtherHeap->MinRoot->LinkToLeft(MinRoot->right);

    // Choose the new minimum for the heap

    if (*(OtherHeap->MinRoot) < *MinRoot)
      MinRoot = OtherHeap->MinRoot;

    // Set the amortized analysis statistics and size of the new heap

    NumNodes += OtherHeap->NumNodes;
    NumMarkedNodes += OtherHeap->NumMarkedNodes;
    NumTrees += OtherHeap->NumTrees;

    // Complete the union by setting the other heap to emptiness
    // then destroying it

    OtherHeap->MinRoot  = NULL;
    OtherHeap->NumNodes = 0;
    OtherHeap->NumTrees = 0;
    OtherHeap->NumMarkedNodes = 0;

    delete OtherHeap;
  }

  bool DecreaseKey(FibonacciNode<T> *theNode, const T& NewKey)
  {
    FibonacciNode<T> Temp;
    Temp.key = NewKey;
    return DecreaseKey(theNode, &Temp);
  }

  bool DecreaseKey(FibonacciNode<T> *theNode, FibonacciNode<T> * NewNode)
  {
    //no increase is approved
    if (theNode==NULL || *theNode < *NewNode)
      return false;

    (*theNode) = (*NewNode);

    FibonacciNode<T> *theParent = theNode->parent;
    if (theParent != NULL && *theNode < *theParent)
    {
      Cut(theNode, theParent);
      CascadingCut(theParent);
    }

    if (*theNode < *MinRoot)
      MinRoot = theNode;

    return true;
  }

  bool Delete(FibonacciNode<T> *theNode)
  {
    if (theNode == NULL) return false;

    FibonacciNode<T> Temp;
    Temp.delete_flag = 1;
    bool Result = DecreaseKey(theNode, Temp);

    if (Result && ExtractMinNode() == NULL)
      Result = false;

    if (Result)
    {
      delete theNode;
      theNode->delete_flag = 0;
    }

    return Result;
  }


  // Extra utility functions
  long GetNumNodes() { return NumNodes; };
  long GetNumTrees() { return NumTrees; };
  long GetNumMarkedNodes() { return NumMarkedNodes; };

  void GetAllNodes(vector<FibonacciNode<T>*> &nodes,FibonacciNode<T> *Tree = NULL, FibonacciNode<T> *theParent=NULL)
  {
    if (Tree == NULL) 
    {
      Tree = MinRoot;
      nodes.clear();
    }

    //siblings
    FibonacciNode<T>* Temp = Tree;
    do {
      nodes.push_back(Temp);
      Temp = Temp->right;
    } while (Temp != NULL && Temp != Tree);

    //children of all the siblings
    Temp = Tree;
    do {
      if (Temp->child != NULL)
        GetAllNodes(nodes, Temp->child, Temp);
      Temp = Temp->right;
    } while (Temp!=NULL && Temp != Tree);
  }

  void Print(FibonacciNode<T> *Tree = NULL, FibonacciNode<T> *theParent=NULL)
  {
    FibonacciNode<T>* Temp = NULL;

    if (Tree == NULL) Tree = MinRoot;

    Temp = Tree;
    do {
      if (Temp->left == NULL)
        zout << "(left is NULL)";
      Temp->Print();
      if (Temp->parent != theParent)
        zout << "(parent is incorrect)";
      if (Temp->right == NULL)
        zout << "(right is NULL)";
      else if (Temp->right->left != Temp)
        zout << "(Error in left link left) ->";
      else zout << " <-> ";

      Temp = Temp->right;

    } while (Temp != NULL && Temp != Tree);
    zout << '\n';

    Temp = Tree;
    do {
      zout << "Children of ";
      Temp->Print();
      zout << ": ";
      if (Temp->child == NULL)
        zout << "NONE\n";
      else Print(Temp->child, Temp);
      Temp = Temp->right;
    } while (Temp!=NULL && Temp != Tree);

    if (theParent == NULL)
    {
      char ch;

      zout << "Done Printing.  Hit a key.\n";
      cin >> ch;
    }
  }

private:

  // Internal functions that help to implement the Standard Operations

  inline void Exchange(FibonacciNode<T>*& N1, FibonacciNode<T>*& N2)
  {
    FibonacciNode<T> *Temp;

    Temp = N1;
    N1 = N2;
    N2 = Temp;
  }

  void Consolidate()
  {
    FibonacciNode<T> *x, *y, *w;
    FibonacciNode<T> *A[1+8*sizeof(long)]; // 1+lg(n)
    int  I=0, Dn = 1+8*sizeof(long);
    short d;

    // Initialize the consolidation detection array

    for (I=0; I < Dn; I++)
      A[I] = NULL;

    // We need to loop through all elements on root list.
    // When a collision of degree is found, the two trees
    // are consolidated in favor of the one with the lesser
    // element key value.  We first need to break the circle
    // so that we can have a stopping condition (we can't go
    // around until we reach the tree we started with
    // because all root trees are subject to becoming a
    // child during the consolidation).

    MinRoot->left->right = NULL;
    MinRoot->left = NULL;
    w = MinRoot;

    do {
      //zout << "Top of Consolidate's loop\n";
      //Print(w);

      x = w;
      d = x->degree;
      w = w->right;

      // We need another loop here because the consolidated result
      // may collide with another large tree on the root list.

      while (A[d] != NULL)
      {
        y = A[d];
        if (*y < *x)
          Exchange(x, y);
        if (w == y) w = y->right;
        Link(y, x);
        A[d] = NULL;
        d++;
        //zout << "After a round of Linking\n";
        //Print(x);
      }
      A[d] = x;

    } while (w != NULL);

    // Now we rebuild the root list, find the new minimum,
    // set all root list nodes' parent pointers to NULL and
    // count the number of subtrees.

    MinRoot = NULL;
    NumTrees = 0;
    for (I = 0; I < Dn; I++)
      if (A[I] != NULL)
        AddToRootList(A[I]);
  }

  void Link(FibonacciNode<T> *y, FibonacciNode<T> *x)
  {
    // Remove node y from root list
    if (y->right != NULL) y->right->left = y->left;
    if (y->left != NULL) y->left->right = y->right;
    NumTrees--;

    // Make node y a singleton circular list with a parent of x
    y->left = y->right = y;
    y->parent = x;

    if (x->child == NULL)     // If node x has no children, then list y is its new child list
      x->child = y;
    else            // Otherwise, node y must be added to node x's child list
      y->LinkToLeft(x->child->right);

    // Increase the degree of node x because it's now a bigger tree
    x->degree ++;

    // Node y has just been made a child, so clear its mark
    if (y->mark) NumMarkedNodes--;
    y->mark = 0;
  }

  void AddToRootList(FibonacciNode<T> *x)
  {
    if (x->mark) NumMarkedNodes --;
    x->mark = 0;
    NumNodes--;
    x->right=x->left=x;
    InsertNode(x);
  }

  // cut x from p
  void Cut(FibonacciNode<T> *x, FibonacciNode<T> *p)
  {
    if (p->child == x) p->child = x->right;
    if (x->right == x) p->child = NULL;
    p->degree --;
    x->Unlink();
    AddToRootList(x);
  }

  void CascadingCut(FibonacciNode<T> *y)
  {
    FibonacciNode<T> *z = y->parent;

    while (z != NULL)
    {
      if (y->mark == 0)
      {
        y->mark = 1;
        NumMarkedNodes++;
        z = NULL;
      }
      else
      {
        Cut(y, z);
        y = z;
        z = y->parent;
      }
    }
  }
};

}


/* test code
void main()
{
  FibonacciHeap<double> heap;
  RandSeed();
  for (int i=0; i<100000; i++)
  heap.Insert(UniformRand<double>(-100000.0,100000.0));
  double x=-MAX_DOUBLE;
  int n=0;
  while(!heap.IsEmpty())
  {
    n++;
    double m=heap.ExtractMin();
    if (x<=m) x=m;
    else
      zout<<x<<' '<<m<<"error!\n";
  }
  zout<<n<<endl;
}
*/
